//
// Created by aquawius on 25-3-14.
//

#ifndef MERGE_SORT
#define MERGE_SORT

#include <algorithm>
#include <iostream>
#include <random>

// 归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。


// 归并排序，稳定排序
// 时间：O(nlog2n) 空间O(n) = O(n) + 1, 这里的1是 O(log2n)[递归占用，相加看作常量1]

void merge(int arr[], int left, int mid, int right)
{
    try {
        int* tempArr = new int[right - left + 1];
        int tempArrIndex = 0;

        // 按找顺序拷贝到数组
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tempArr[tempArrIndex++] = arr[i++];
            } else {
                tempArr[tempArrIndex++] = arr[j++];
            }
        }

        // 判断剩余
        while (i <= mid) {
            tempArr[tempArrIndex++] = arr[i++];
        }

        while (j <= right) {
            tempArr[tempArrIndex++] = arr[j++];
        }

        // 拷贝到原数组中
        for (i = left, j = 0; i <= right; i++, j++) {
            arr[i] = tempArr[j];
        }

        delete[] tempArr;

    } catch (const std::bad_alloc& e) {
        std::cout << e.what() << std::endl;
    } catch (...) {
        std::cout << "Unknown exception" << std::endl;
    }
}

void mergeSort(int arr[], int begin, int end)
{
    if (begin >= end) {
        return;
    }

    // 先递
    int mid = (begin + end) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);

    // 后归, 把 [begin, mid] , [mid + 1, end] 合并成一个大的
    merge(arr, begin, mid, end);
}

void mergeSort(int arr[], int arrSize)
{
    mergeSort(arr, 0, arrSize - 1);
}

int main(int argc, char** argv)
{
    std::random_device rd;
    std::default_random_engine engine(rd());
    std::uniform_int_distribution<int> dis(0, 100);

    static constexpr int MAX_ARRAY_SIZE = 50;

    const auto arr = new int[MAX_ARRAY_SIZE];

    for (int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        arr[i] = dis(engine);
    }

    std::for_each(arr, arr + MAX_ARRAY_SIZE, [](const int a) { std::cout << a << ' '; });

    std::cout << std::endl;

    mergeSort(arr, MAX_ARRAY_SIZE);

    std::for_each(arr, arr + MAX_ARRAY_SIZE, [](const int a) { std::cout << a << ' '; });

    // 释放动态分配的内存
    delete[] arr;

    return 0;
}

#endif // MERGE_SORT